package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.List;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-23 09:23
 */
public class AY440字典序第K小数字 {

    public static void main(String[] args) {

        int n = 100;
        int k = 10;
        System.out.println(findKthNumber(n, k));
    }

    public static int findKthNumber(int n, int k) {
        List<Integer> list = new ArrayList<>();
        findKthNumber(n, k, list);
        int total = 0;
        for (int i = list.size() - 1; i >= 0; i--) {
            total += list.get(i) * Math.pow(10, list.size() - 1 - i);
        }
        return total;
    }

    /**
     * 1.如果直接使用字符串排序的话 时间复杂度是 f(n) 如果n太大耗时太久
     * 2.找规律
     * 1.字典序是按照首字符排序的 1,2,3,4,5,6,7,8,9 只要计算出每个字母开头的数字分别占多少即可
     * 先找出第一个首字符是多少 再根据k剩余数 继续寻找下一个首字符
     * 如果第一个首字符 小于n的首字符 则 在n位数个数中寻找
     * 例： n = 2220000   寻找到的首字符是 1 则相当于在999999中寻找k位数
     * 2 则相当于在220000中寻找k-[所有1的可能数]
     * 3 则相当于在999999中寻找k-[所有1,2的可能数]
     *
     * @param n
     * @param k
     * @return
     */
    public static void findKthNumber(int n, int k, List<Integer> list) {
        if (list.size() != 0) {
            if (k == 1) {
                list.add(0);
                return;
            }
            k--;
        }
        //求出1到9每个总数
        int[] dp = getInts(n);
        String sn = n + "";
        //获取n的首数字
        int nFirst = sn.charAt(0) - 48;
        //获取n的位数
        int nTimes = sn.length();
        int i;
        for (i = 0; i < 10; i++) {
            k -= dp[i];
            if (k <= 0) {
                break;
            }
        }
        int first = i + 1;
        list.add(first);
        k = dp[i] + k;
        if (k == 1) {
            //如果k=1 则说明数据已找到
            return;
        }
        //如果和首字母一样
        if (first > nFirst) {
            findKthNumber((int) Math.pow(10, nTimes - 2) - 1, k - 1, list);
        } else if (first < nFirst) {
            findKthNumber((int) Math.pow(10, nTimes - 2) - 1, k - 1, list);
        } else {
            findKthNumber(n - nFirst * (int) Math.pow(10, nTimes - 1), k - 1, list);
        }
    }

    /**
     * 获取 每个字符开头的个数
     *
     * @param n
     * @return
     */
    private static int[] getInts(int n) {
        int[] dp = new int[9];
        //9 每个数分别有一个 99每个数分别有11个 999每个数分别有111
        int m = 9;
        while (n > m) {
            m = 10 * m + 9;
        }
        //每个数最少有m/10个
        m = (m - 9) / 10;
        Boolean flag = true;
        //再往后 每隔m+1个 就是下一个字符的剩余数
        n = n - m;
        for (int i = 0; i < 9; i++) {
            if (flag) {
                n = n - (m + 1);
                if (n > 0) {
                    dp[i] = m / 9 + (m + 1);
                } else {
                    dp[i] = m / 9 + (m + 1 + n);
                    flag = false;
                }
            } else {
                dp[i] = m / 9;
            }
        }
        return dp;
    }
}
